const arr = Array.from({ length: 1000000 }, () => Math.floor(Math.random() * 1000000) + 1)

function bucketSort(nums, bucketCount) {
  let max = -Infinity
  let min = Infinity
  for (let i = 0; i < nums.length; i++) {
    max = Math.max(max, nums[i])
    min = Math.min(min, nums[i])
  }
  const bucketSize = Math.floor((max - min) / bucketCount) + 1
  const bucket = Array.from({ length: bucketCount }, () => [])
  for (let i = 0; i < nums.length; i++) {
    const idx = Math.floor((nums[i] - min) / bucketSize)
    bucket[idx].push(nums[i])
  }
  const res = []
  for (let i = 0; i < bucketCount; i++) {
    if (bucket[i].length > 0) {
      bucket[i].sort((a, b) => a - b)
      for (let j = 0; j < bucket[i].length; j++) {
        res.push(bucket[i][j])
      }
    }
  }
  return res
}

// 理论上，桶的数量越多，排序的速度越快
// 但是桶的数量不能太多，否则会导致创建桶的时间过长
// 以一百万个数据为例，最优的桶的数量大概在 86686 左右
const start = Date.now()
bucketSort(arr, 86686)
console.log('桶排序', Date.now() - start);

// 使用内置排序进行对比
const start2 = Date.now()
arr.sort((a, b) => a - b)
console.log('内置排序', Date.now() - start)